

/**
 * QuadTree object.
 *
 * The quadrant indexes are numbered as below:
 * y
 * ↑    |
 * | 1  |  0
 * |----+----
 * | 2  |  3
 * |    |
 * 0-------->x
 *
 * 先建立Bound类
 * 使用insert创建树
 * 使用findObjects获取可能碰撞的物体
 * 自行测试碰撞
 */
export class QuadTree {
    /**
     * 区域表示
     */
    bound: QuadTreeBound;
    /**
     * 子节点队列
     */
    children: QuadTree[];
    /**
     * 当前节点对象，关注其bound
     */
    objects: QuadTreeBound[];
    level: number;
    /**
     * 最大层数，与单元格内容忍的物体数制约
     */
    maxLevel = 5; // 4**5 = 1024

    config: {
        /**
         * 单元格内容忍的物体数，超出则进行更细致的划分
         */
        perBoundMaxObjectNumber: number
    } = {
            perBoundMaxObjectNumber: 30,
        }

    constructor(boundBox: QuadTreeBound, level?: number, config?: { perBoundMaxObjectNumber?: number }) {
        this.bound = boundBox || new QuadTreeBound();
        this.level = level || 0;
        this.objects = [];
        this.children = [];
        if (config && config.perBoundMaxObjectNumber) {
            this.config.perBoundMaxObjectNumber = config.perBoundMaxObjectNumber
        }
    }

    /*
     * Clears the quadTree and all nodes of objects
     */
    clear():void {
        this.objects = [];
        for (const node of this.children) {
            node.clear();
        }
        this.children = [];
    }

    /*
     * Get all objects in the quadTree
     */
    getAllObjects(returnedObjects: QuadTreeBound[]):QuadTreeBound[] {
        for (const node of this.children) {
            node.getAllObjects(returnedObjects);
        }
        for (const obj of this.objects) {
            returnedObjects.push(obj);
        }
        return returnedObjects;
    }

    /*
     * 返回树上与提供bound可能碰撞的bounds
     */
    findObjects(returnedObjects: QuadTreeBound[], obj: QuadTreeBound): QuadTreeBound[] {
        if (typeof obj === "undefined") {
            console.log("UNDEFINED OBJECT");
            return [];
        }

        const index = this.getFittedChildNodeIndex(obj);
        if (index != -1 && this.children.length) {
            return this.children[index].findObjects(returnedObjects, obj);
        }

        return this.getAllObjects(returnedObjects);
    }

    /*
     * 建立四叉树
     */
    insert(obj?: QuadTreeBound):void {
        if (typeof obj === "undefined") {
            return;
        }

        // 如果有子节点
        if (this.children.length) {
            const index = this.getFittedChildNodeIndex(obj);
            if (index != -1) {
                this.children[index].insert(obj);
                return;
            }
        }

        this.objects.push(obj);

        if (this.objects.length > this.config.perBoundMaxObjectNumber && this.level < this.maxLevel) {
            if (this.children[0] == null) {
                this.split();
            }
            let i = 0;
            while (i < this.objects.length) {
                const index = this.getFittedChildNodeIndex(this.objects[i]);
                if (index == -1) {
                    i++;
                }
                else {
                    this.children[index].insert((this.objects.splice(i, 1))[0]);
                }
            }
        }
    }

    private getFittedChildNodeIndex(obj: QuadTreeBound):3 | 2 | 1 | 0 | -1 {
        const xMidpoint = this.bound.x + this.bound.width / 2; // 横向子节点
        const yMidpoint = this.bound.y + this.bound.height / 2; // 纵向子节点
        const withinX = obj.x + obj.width < xMidpoint;
        const withinY = obj.y + obj.height < yMidpoint;
        const overX = obj.x >= xMidpoint;
        const overY = obj.y >= yMidpoint;
        if (overX && withinY) return 3;
        if (withinX && withinY) return 2;
        if (withinX && overY) return 1;
        if (overX && overY) return 0;
        return -1;
    }

    private split():void {
        const subWidth = (this.bound.width / 2) | 0;
        const subHeight = (this.bound.height / 2) | 0;
        const childLevel = this.level + 1;
        this.children[3] = new QuadTree(
            new QuadTreeBound(this.bound.x + subWidth, this.bound.y, subWidth, subHeight),
            childLevel, this.config
        );
        this.children[2] = new QuadTree(
            new QuadTreeBound(this.bound.x, this.bound.y, subWidth, subHeight),
            childLevel, this.config
        );
        this.children[1] = new QuadTree(
            new QuadTreeBound(this.bound.x, this.bound.y + subHeight, subWidth, subHeight),
            childLevel, this.config
        );
        this.children[0] = new QuadTree(
            new QuadTreeBound(this.bound.x + subWidth, this.bound.y + subHeight, subWidth, subHeight),
            childLevel, this.config
        );
    }
}

export class QuadTreeBound {
    x: number;
    y: number;
    width: number;
    height: number;
    userData?: any;
    constructor(x = 0, y = 0, width = 0, height = 0, userData?: any) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.userData = userData;
    }
}

